#include <iostream>
#include <vector>
using namespace std;
 
 
/*
        Designed to help solve large logic puzzles of the constraint matrix type.
*/
 
class LogicConstraintMatrix
{
        int _class_count;
        int _house_count;
        int _stride;
 
        // Stored class-first, so first house classes are the first few elements
        // Stored row-first, so first row are the first few elements
        char *_matrix;
        static const char CH_CLEAR = ' ';
        static const char CH_YES = 'O';
        static const char CH_NO = 'x';
 
        char &Get(int class_row, int house_row, int class_col, int house_col)
        {
                int row = class_row * _house_count + house_row;
                int col = class_col * _house_count + house_col;
                return _matrix[row * _stride + col];
        }
 
        void Cleanup()
        {
                if (_matrix)
                {
                        delete []_matrix;
                        _matrix = 0;
                }
        }
 
        bool VerifySymmetric()
        {
                for (int class_row = 0; class_row < _class_count; ++class_row)
                {
                        for (int house_row = 0; house_row < _house_count; ++house_row)
                        {
                                for (int class_col = 0; class_col < _class_count; ++class_col)
                                {
                                        for (int house_col = 0; house_col < _house_count; ++house_col)
                                        {
                                                if (Get(class_row, house_row, class_col, house_col) != Get(class_col, house_col, class_row, house_row))
                                                {
                                                        cout << "Failure at " << class_row << ":" << house_row << ", " << class_col << ":" << house_col << endl;
                                                        return false;
                                                }
                                        }
                                }
                        }
                }
 
                return true;
        }
 
        bool MirrorEquivalencies()
        {
                cout << "Running MirrorEquivs on this matrix:" << endl;
                Print();
 
                bool modified = false;
 
                for (int class_row = 0; class_row < _class_count; ++class_row)
                {
                        for (int house_row = 0; house_row < _house_count; ++house_row)
                        {
                                for (int class_col = 0; class_col < _class_count; ++class_col)
                                {
                                        if (class_row == class_col)
                                        {
                                                // Skip diagonals
                                                continue;
                                        }
 
                                        for (int house_col = 0; house_col < _house_count; ++house_col)
                                        {
                                                if (Get(class_row, house_row, class_col, house_col) == CH_YES)
                                                {
                                                        bool changed = false;
                                                        for (int class_row_ii = 0; class_row_ii < _class_count; ++class_row_ii)
                                                        {
                                                                for (int house_row_ii = 0; house_row_ii < _house_count; ++house_row_ii)
                                                                {
                                                                        char &state_a = Get(class_row_ii, house_row_ii, class_col, house_col);
                                                                        char &state_b = Get(class_row_ii, house_row_ii, class_row, house_row);
                                                                        if (state_a != state_b)
                                                                        {
                                                                                if ( (state_a == CH_YES && state_b == CH_NO) ||
                                                                                         (state_a == CH_NO && state_b == CH_YES) )
                                                                                {
                                                                                        cout << "ERROR IN INPUT: Logical fault!! Column " << class_row << ":" << house_row << " and " << class_col << ":" << house_col << " should match" << endl;
                                                                                        cin.get();
                                                                                        return false;
                                                                                }
 
                                                                                if (state_a == CH_CLEAR)
                                                                                        state_a = state_b;
                                                                                else
                                                                                        state_b = state_a;
                                                                                if (!changed)
                                                                                {
                                                                                        changed = true;
                                                                                        cout << "Column " << class_row << ":" << house_row << " and " << class_col << ":" << house_col << " should match" << endl;
                                                                                }
                                                                                modified = true;
                                                                                cout << "--Fixed one at row " << class_row_ii << ":" << house_row_ii << endl;
                                                                        }
                                                                }
                                                        }
 
                                                        if (changed)
                                                        {
                                                                Print();
                                                        }
 
                                                        changed = false;
                                                        for (int class_col_ii = 0; class_col_ii < _class_count; ++class_col_ii)
                                                        {
                                                                for (int house_col_ii = 0; house_col_ii < _house_count; ++house_col_ii)
                                                                {
                                                                        char &state_a = Get(class_row, house_row, class_col_ii, house_col_ii);
                                                                        char &state_b = Get(class_col, house_col, class_col_ii, house_col_ii);
                                                                        if (state_a != state_b)
                                                                        {
                                                                                if ( (state_a == CH_YES && state_b == CH_NO) ||
                                                                                         (state_a == CH_NO && state_b == CH_YES) )
                                                                                {
                                                                                        cout << "ERROR IN INPUT: Logical fault!! Row " << class_row << ":" << house_row << " and " << class_col << ":" << house_col << " should match" << endl;
                                                                                        cin.get();
                                                                                        return false;
                                                                                }
 
                                                                                if (state_a == CH_CLEAR)
                                                                                        state_a = state_b;
                                                                                else
                                                                                        state_b = state_a;
                                                                                if (!changed)
                                                                                {
                                                                                        changed = true;
                                                                                        cout << "Row " << class_row << ":" << house_row << " and " << class_col << ":" << house_col << " should match" << endl;
                                                                                }
                                                                                modified = true;
                                                                                cout << "--Fixed one at column " << class_col_ii << ":" << house_col_ii << endl;
                                                                        }
                                                                }
                                                        }
 
                                                        if (changed)
                                                        {
                                                                Print();
                                                        }
                                                }
                                        }
                                }
                        }
                }
 
                if (!VerifySymmetric())
                {
                        cout << "Failure in MirrorEquivalencies" << endl;
                        Print();
                        cin.get();
                        return false;
                }
 
                return modified;
        }
 
        bool ProcessOfElimination()
        {
                cout << "Running ProcessOfElimination on this matrix:" << endl;
                Print();
 
                bool modified = false;
 
                for (int class_row = 0; class_row < _class_count; ++class_row)
                {
                        for (int class_col = 0; class_col < _class_count; ++class_col)
                        {
                                if (class_row == class_col)
                                {
                                        // Skip diagonals
                                        continue;
                                }
 
                                for (int house_row = 0; house_row < _house_count; ++house_row)
                                {
                                        int count = 0;
                                        int house = 0;
 
                                        for (int house_col = 0; house_col < _house_count; ++house_col)
                                        {
                                                switch (Get(class_row, house_row, class_col, house_col))
                                                {
                                                case CH_NO:
                                                        ++count;
                                                        break;
                                                case CH_YES:
                                                        count = 0;
                                                        house_col = _house_count; // break loop
                                                        break;
                                                default:
                                                        house = house_col;
                                                        break;
                                                }
                                        }
 
                                        if (count == _house_count - 1)
                                        {
                                                cout << "Process of elimination found a row at " << class_row << ":" << house_row << ", " << class_col << ":" << house << endl;
                                                Yes(class_row, house_row, class_col, house);
                                                modified = true;
                                                Print();
                                        }
 
                                        if (count >= _house_count)
                                        {
                                                cout << "ERROR all Xes in row " << class_row << ":" << house_row << endl;
                                                cin.get();
                                                return false;
                                        }
                                }
 
                                for (int house_col = 0; house_col < _house_count; ++house_col)
                                {
                                        int count = 0;
                                        int house = 0;
 
                                        for (int house_row = 0; house_row < _house_count; ++house_row)
                                        {
                                                switch (Get(class_row, house_row, class_col, house_col))
                                                {
                                                case CH_NO:
                                                        ++count;
                                                        break;
                                                case CH_YES:
                                                        count = 0;
                                                        house_row = _house_count; // break loop
                                                        break;
                                                default:
                                                        house = house_row;
                                                        break;
                                                }
                                        }
 
                                        if (count == _house_count - 1)
                                        {
                                                cout << "Process of elimination found a column at " << class_row << ":" << house << ", " << class_col << ":" << house_col << endl;
                                                Yes(class_row, house, class_col, house_col);
                                                modified = true;
                                                Print();
                                        }
 
                                        if (count >= _house_count)
                                        {
                                                cout << "ERROR all Xes in column " << class_col << ":" << house_col << endl;
                                                cin.get();
                                                return false;
                                        }
                                }
                        }
                }
 
                if (!VerifySymmetric())
                {
                        cout << "ERROR: Failure in ProcessOfElimination" << endl;
                        Print();
                        cin.get();
                        return false;
                }
 
                return modified;
        }
 
        bool ApplyNeighborRule(int class_row_a, int house_row_a, int class_row_b, int house_row_b, int position_class_col, int compare_type)
        {
                /*
                        CompareType : negative means A is to the left of B
                */
                bool modified = false;
 
                for (int house_col_a = 0; house_col_a < _house_count; ++house_col_a)
                {
                        char state = Get(class_row_a, house_row_a, position_class_col, house_col_a);
 
                        if (state == CH_CLEAR)
                        {
                                bool possible = false;
 
                                if (house_col_a > 0 && compare_type >= 0)
                                {
                                        char state_left = Get(class_row_b, house_row_b, position_class_col, house_col_a - 1);
 
                                        if (state_left != CH_NO)
                                                possible = true;
                                }
                                if (house_col_a < _house_count - 1 && compare_type <= 0)
                                {
                                        char state_right = Get(class_row_b, house_row_b, position_class_col, house_col_a + 1);
 
                                        if (state_right != CH_NO)
                                                possible = true;
                                }
 
                                if (!possible)
                                {
                                        No(class_row_a, house_row_a, position_class_col, house_col_a);
                                        cout << "Neighbor rule A: Found an impossible position at " << class_row_a << ":" << house_row_a << ", " << position_class_col << ":" << house_col_a << endl;
                                        modified = true;
                                        Print();
                                }
                        }
                }
 
                for (int house_col_b = 0; house_col_b < _house_count; ++house_col_b)
                {
                        char state = Get(class_row_b, house_row_b, position_class_col, house_col_b);
 
                        if (state == CH_CLEAR)
                        {
                                bool possible = false;
 
                                if (house_col_b > 0 && compare_type <= 0)
                                {
                                        char state_left = Get(class_row_a, house_row_a, position_class_col, house_col_b - 1);
 
                                        if (state_left != CH_NO)
                                                possible = true;
                                }
                                if (house_col_b < _house_count - 1 && compare_type >= 0)
                                {
                                        char state_right = Get(class_row_a, house_row_a, position_class_col, house_col_b + 1);
 
                                        if (state_right != CH_NO)
                                                possible = true;
                                }
 
                                if (!possible)
                                {
                                        No(class_row_b, house_row_b, position_class_col, house_col_b);
                                        cout << "Neighbor rule B: Found an impossible position at " << class_row_b << ":" << house_row_b << ", " << position_class_col << ":" << house_col_b << endl;
                                        modified = true;
                                        Print();
                                }
                        }
                }
 
                return modified;
        }
 
        struct NeighborRule
        {
                int class_row_a, house_row_a, class_row_b, house_row_b, position_class_col;
                int compare_type;
        };
 
        std::vector<NeighborRule> _neighbor_rules;
 
        bool ApplyNeighborRules()
        {
                bool modified = false;
 
                for (int ii = 0; ii < _neighbor_rules.size(); ++ii)
                {
                        NeighborRule &rule = _neighbor_rules[ii];
 
                        modified |= ApplyNeighborRule(rule.class_row_a, rule.house_row_a, rule.class_row_b, rule.house_row_b, rule.position_class_col, rule.compare_type);
                }
 
                if (!VerifySymmetric())
                {
                        cout << "ERROR: Failure in ApplyNeighborRules" << endl;
                        Print();
                        cin.get();
                        return false;
                }
 
                return modified;
        }
 
public:
        LogicConstraintMatrix(int class_count, int house_count)
        {
                _class_count = class_count;
                _house_count = house_count;
                _stride = house_count * class_count;
 
                _matrix = new char[_stride * _stride];
 
                Clear();
        }
        ~LogicConstraintMatrix()
        {
                Cleanup();
        }
 
        bool Valid()
        {
                return _matrix != 0;
        }
 
        void Clear()
        {
                for (int class_row = 0; class_row < _class_count; ++class_row)
                {
                        for (int house_row = 0; house_row < _house_count; ++house_row)
                        {
                                for (int class_col = 0; class_col < _class_count; ++class_col)
                                {
                                        for (int house_col = 0; house_col < _house_count; ++house_col)
                                        {
                                                if (class_row == class_col)
                                                {
                                                        if (house_row == house_col)
                                                        {
                                                                Get(class_row, house_row, class_col, house_col) = CH_YES;
                                                        }
                                                        else
                                                        {
                                                                Get(class_row, house_row, class_col, house_col) = CH_NO;
                                                        }
                                                }
                                                else
                                                {
                                                        Get(class_row, house_row, class_col, house_col) = CH_CLEAR;
                                                }
                                        }
                                }
                        }
                }
 
                _neighbor_rules.clear();
        }
 
        // CompareType < 0 means A must be directly left of B
        // CompareType > 0 means A must be directly right of B
        // CompareType = 0 means A is either directly left or right of B
        void AddNeighborRule(int class_row_a, int house_row_a, int class_row_b, int house_row_b, int position_class_col, int compare_type)
        {
                NeighborRule rule = { class_row_a, house_row_a, class_row_b, house_row_b, position_class_col, compare_type };
 
                _neighbor_rules.push_back(rule);
        }
 
        void Print()
        {
                for (int class_row = 0; class_row < _class_count; ++class_row)
                {
                        for (int house_row = 0; house_row < _house_count; ++house_row)
                        {
                                cout << class_row << ":" << house_row << "=";
 
                                for (int class_col = 0; class_col < _class_count; ++class_col)
                                {
                                        for (int house_col = 0; house_col < _house_count; ++house_col)
                                        {
                                                cout << Get(class_row, house_row, class_col, house_col);
                                        }
 
                                        cout << ' ';
                                }
 
                                cout << endl;
                        }
 
                        cout << endl;
                }
        }
 
        void Yes(int class_row, int house_row, int class_col, int house_col)
        {
                for (int house_row_ii = 0; house_row_ii < _house_count; ++house_row_ii)
                        Get(class_row, house_row_ii, class_col, house_col) = CH_NO;
 
                for (int house_col_ii = 0; house_col_ii < _house_count; ++house_col_ii)
                        Get(class_row, house_row, class_col, house_col_ii) = CH_NO;
 
                Get(class_row, house_row, class_col, house_col) = CH_YES;
 
                for (int house_col_ii = 0; house_col_ii < _house_count; ++house_col_ii)
                        Get(class_col, house_col_ii, class_row, house_row) = CH_NO;
 
                for (int house_row_ii = 0; house_row_ii < _house_count; ++house_row_ii)
                        Get(class_col, house_col, class_row, house_row_ii) = CH_NO;
 
                Get(class_col, house_col, class_row, house_row) = CH_YES;
        }
 
        void No(int class_row, int house_row, int class_col, int house_col)
        {
                Get(class_row, house_row, class_col, house_col) = CH_NO;
                Get(class_col, house_col, class_row, house_row) = CH_NO;
        }
 
        void Solve()
        {
                cout << "Initial state:" << endl;
                Print();
 
                if (!VerifySymmetric())
                {
                        cout << "Failure in setup" << endl;
                        return;
                }
 
                int round = 0;
                while (MirrorEquivalencies() || ProcessOfElimination() || ApplyNeighborRules())
                {
                        cout << endl << "After round " << ++round << ":" << endl;
                        Print();
                }
 
                cout << "Halted.  Cannot solve further." << endl;
        }
 
        int GetSolution(int class_row, int house_row, int class_col)
        {
                for (int house_col = 0; house_col < _house_count; ++house_col)
                {
                        if (Get(class_row, house_row, class_col, house_col) == CH_YES)
                        {
                                return house_col;
                        }
                }
 
                return -1;
        }
};
 
int main()
{
        LogicConstraintMatrix einstein(6, 5);
 
        if (!einstein.Valid())
        {
                cerr << "Invalid solver instance" << endl;
                return 1;
        }
 
 
        enum Classes
        {
                CL_NATION, CL_BEVERAGE, CL_CIGAR, CL_PET, CL_HOUSE_NUMBER, CL_HOUSE_COLOR
        };
 
        enum Nations
        {
                NAT_BRITISH, NAT_SWEDISH, NAT_DANISH, NAT_NORWEGIAN, NAT_GERMAN
        };
 
        enum Beverages
        {
                BEV_TEA, BEV_COFFEE, BEV_MILK, BEV_BEER, BEV_WATER
        };
 
        enum Cigars
        {
                CIG_PALL_MALL, CIG_DUNHILL, CIG_BLENDS, CIG_BLUE_MASTER, CIG_PRINCE
        };
 
        enum Pets
        {
                PET_DOG, PET_FISH, PET_BIRD, PET_CAT, PET_HORSE
        };
 
        enum HouseNumbers
        {       // from left to right and first to last:
                NUM_1, NUM_2, NUM_3, NUM_4, NUM_5
        };
 
        enum HouseColors
        {
                COL_RED, COL_GREEN, COL_WHITE, COL_YELLOW, COL_BLUE
        };
 
 
        einstein.Yes(CL_NATION, NAT_BRITISH, CL_HOUSE_COLOR, COL_RED);
        einstein.Yes(CL_NATION, NAT_SWEDISH, CL_PET, PET_DOG);
        einstein.Yes(CL_NATION, NAT_DANISH, CL_BEVERAGE, BEV_TEA);
        einstein.AddNeighborRule(CL_HOUSE_COLOR, COL_GREEN, CL_HOUSE_COLOR, COL_WHITE, CL_HOUSE_NUMBER, -1);
        einstein.Yes(CL_HOUSE_COLOR, COL_GREEN, CL_BEVERAGE, BEV_COFFEE);
        einstein.Yes(CL_CIGAR, CIG_PALL_MALL, CL_PET, PET_BIRD);
        einstein.Yes(CL_HOUSE_COLOR, COL_YELLOW, CL_CIGAR, CIG_DUNHILL);
        einstein.Yes(CL_HOUSE_NUMBER, NUM_3, CL_BEVERAGE, BEV_MILK);
        einstein.Yes(CL_NATION, NAT_NORWEGIAN, CL_HOUSE_NUMBER, NUM_1);
        einstein.AddNeighborRule(CL_CIGAR, CIG_BLENDS, CL_PET, PET_CAT, CL_HOUSE_NUMBER, 0);
        einstein.AddNeighborRule(CL_PET, PET_HORSE, CL_CIGAR, CIG_DUNHILL, CL_HOUSE_NUMBER, 0);
        einstein.Yes(CL_CIGAR, CIG_BLUE_MASTER, CL_BEVERAGE, BEV_BEER);
        einstein.Yes(CL_NATION, NAT_GERMAN, CL_CIGAR, CIG_PRINCE);
        einstein.AddNeighborRule(CL_NATION, NAT_NORWEGIAN, CL_HOUSE_COLOR, COL_BLUE, CL_HOUSE_NUMBER, 0);
        einstein.AddNeighborRule(CL_CIGAR, CIG_BLENDS, CL_BEVERAGE, BEV_WATER, CL_HOUSE_NUMBER, 0);
 
        einstein.Solve();
 
        int nation = einstein.GetSolution(CL_PET, PET_FISH, CL_NATION);
 
        switch (nation)
        {
        case NAT_BRITISH:
                cout << "Brit owns the fish." << endl;
                break;
        case NAT_SWEDISH:
                cout << "Swede owns the fish." << endl;
                break;
        case NAT_DANISH:
                cout << "Dane owns the fish." << endl;
                break;
        case NAT_NORWEGIAN:
                cout << "Norwegian owns the fish." << endl;
                break;
        case NAT_GERMAN:
                cout << "German owns the fish." << endl;
                break;
        }
 
        cin.get();
 
        return 0;
}
 
 
/*
        Program output:
 
        0:0=Oxxxx xxOxx Oxxxx xxOxx xxOxx Oxxxx
        0:1=xOxxx xxxOx xxxOx Oxxxx xxxxO xxOxx
        0:2=xxOxx Oxxxx xxOxx xxxxO xOxxx xxxxO
        0:3=xxxOx xxxxO xOxxx xxxOx Oxxxx xxxOx
        0:4=xxxxO xOxxx xxxxO xOxxx xxxOx xOxxx
 
        1:0=xxOxx Oxxxx xxOxx xxxxO xOxxx xxxxO
        1:1=xxxxO xOxxx xxxxO xOxxx xxxOx xOxxx
        1:2=Oxxxx xxOxx Oxxxx xxOxx xxOxx Oxxxx
        1:3=xOxxx xxxOx xxxOx Oxxxx xxxxO xxOxx
        1:4=xxxOx xxxxO xOxxx xxxOx Oxxxx xxxOx
 
        2:0=Oxxxx xxOxx Oxxxx xxOxx xxOxx Oxxxx
        2:1=xxxOx xxxxO xOxxx xxxOx Oxxxx xxxOx
        2:2=xxOxx Oxxxx xxOxx xxxxO xOxxx xxxxO
        2:3=xOxxx xxxOx xxxOx Oxxxx xxxxO xxOxx
        2:4=xxxxO xOxxx xxxxO xOxxx xxxOx xOxxx
 
        3:0=xOxxx xxxOx xxxOx Oxxxx xxxxO xxOxx
        3:1=xxxxO xOxxx xxxxO xOxxx xxxOx xOxxx
        3:2=Oxxxx xxOxx Oxxxx xxOxx xxOxx Oxxxx
        3:3=xxxOx xxxxO xOxxx xxxOx Oxxxx xxxOx
        3:4=xxOxx Oxxxx xxOxx xxxxO xOxxx xxxxO
 
        4:0=xxxOx xxxxO xOxxx xxxOx Oxxxx xxxOx
        4:1=xxOxx Oxxxx xxOxx xxxxO xOxxx xxxxO
        4:2=Oxxxx xxOxx Oxxxx xxOxx xxOxx Oxxxx
        4:3=xxxxO xOxxx xxxxO xOxxx xxxOx xOxxx
        4:4=xOxxx xxxOx xxxOx Oxxxx xxxxO xxOxx
 
        5:0=Oxxxx xxOxx Oxxxx xxOxx xxOxx Oxxxx
        5:1=xxxxO xOxxx xxxxO xOxxx xxxOx xOxxx
        5:2=xOxxx xxxOx xxxOx Oxxxx xxxxO xxOxx
        5:3=xxxOx xxxxO xOxxx xxxOx Oxxxx xxxOx
        5:4=xxOxx Oxxxx xxOxx xxxxO xOxxx xxxxO
 
        Halted.  Cannot solve further.
        German owns the fish.
*/